//110. 平衡二叉树
//思路：1. 我们将一个二叉树看作左右两颗子树，先看左右两颗大的子树相差是否大于1，大于1就返回false
//2. 再以第一个左子树节点作为根节点往下走，不断递归
//3. 最后以第一个右子树节点作为根节点往下走，不断递归
//注意：这里计算二叉树高度是核心，三个步骤是并且关系，当三个都成立时二叉树才是平衡二叉树

#include <stdlib.h>
#include <stdbool.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};
int TreeHeight(struct TreeNode* root)
{
    if (NULL == root)
        return 0;

    int leftH = TreeHeight(root->left);
    int rightH = TreeHeight(root->right);

    return leftH > rightH ? leftH + 1 : rightH + 1;
}
bool isBalanced(struct TreeNode* root) {
    if (NULL == root)
        return true;

    return abs(isBalanced(root->left) - isBalanced(root->right)) <= 1
        && isBalanced(root->left) && isBalanced(root->right);
}